package com.example.arithmeticleetcode.leetcode.jan;

import com.alibaba.fastjson.JSON;

import java.awt.*;
import java.io.IOException;
import java.net.URI;
import java.util.*;
import java.util.List;
import java.util.stream.Collectors;

/**
 * @program: arithmetic-leetcode
 * @description:
 * @author: FangZhen
 * @create: 2021-01-26 09:13
 **/
public class Demo21 {

    public Demo21() {

    }

    /**
     * 剑指 Offer 55 - I. 二叉树的深度
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int deep = 0;
        while (!queue.isEmpty()) {
            int size = queue.size();
            deep++;
            for (int i = 0; i < size; i++) {
                TreeNode node = queue.poll();
                if (node == null) continue;
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
            }
        }
        return deep;
    }

    /**
     * 剑指 Offer 27. 二叉树的镜像
     *
     * @param root
     * @return
     */
    public TreeNode mirrorTree(TreeNode root) {
        return null;
    }

    /**
     * 剑指 Offer 22. 链表中倒数第k个节点
     *
     * @param head
     * @param k
     * @return
     */
    public ListNode getKthFromEnd(ListNode head, int k) {
        if (head == null) return null;
        ListNode cur = head;
        int count = 1;
        while (cur != null) {
            count++;
            cur = cur.next;
        }
        int preK = count - k;

        while (preK-- > 1 && head != null) {
            head = head.next;
        }
        ListNode retNode = head.next;
        head = null;
        return retNode;

    }


    /**
     * 剑指 Offer 15. 二进制中1的个数
     *
     * @param n
     * @return
     */
    public int hammingWeight(int n) {
        String s = Integer.toBinaryString(n);
        char[] chars = s.toCharArray();
        int count = 0;
        for (char aChar : chars) {
            if (aChar == '1') count++;
        }
        return count;
    }

    public static void main(String[] args) throws IOException {
        String workUnitIdStr = "[]";
        //格式为[1,2,3],需要截取中间的数据
        String substring = workUnitIdStr.substring(1, workUnitIdStr.length() - 1);
        if (substring == null) System.out.println("为空");
        if (substring instanceof String) System.out.println("为空字符串");
        System.out.println("------");
        System.out.println(substring);
    }

    /**
     * 1128. 等价多米诺骨牌对的数量
     *
     * @param dominoes
     * @return
     */
    public static int numEquivDominoPairs(int[][] dominoes) {
        int[] usedIndex = new int[dominoes.length];
        int count = 0;
        int sum = 0;
        for (int i = 0; i < dominoes.length; i++) {
            if (usedIndex[i] > 0) continue;
            if (count > 0) {
                sum += (count * (count + 1) >> 1);
                count = 0;
            }
            for (int j = i + 1; j < dominoes.length; j++) {
                if (usedIndex[j] > 0) continue;
                if ((dominoes[i][0] == dominoes[j][0] && dominoes[i][1] == dominoes[j][1])
                        || (dominoes[i][0] == dominoes[j][1] && dominoes[i][1] == dominoes[j][0])) {
                    usedIndex[i]++;
                    usedIndex[j]++;
                    count++;
                }
            }
        }
        sum += (count * (count + 1) >> 1);
        return sum;
    }


    public int hammingWeight2(int n) {
        int bits = 0;
        int mask = 1;
        for (int i = 0; i < 32; i++) {
            if ((n & mask) != 0) bits++;
            mask <<= 1;
        }
        return bits;
    }

    public int hammingWeight3(int n) {
        int sum = 0;
        while (n != 0) {
            sum++;
            n &= (n - 1);
        }
        return sum;
    }


    /**
     * 面试题 16.11. 跳水板
     *
     * @param shorter
     * @param longer
     * @param k
     * @return
     */
    public int[] divingBoard(int shorter, int longer, int k) {
        if (k == 0) return new int[0];
        List<Integer> list = new ArrayList<>();
        for (int i = 0; i <= k; i++) {
            list.add(i * shorter + (k - i) * longer);
        }
        int[] ints = new int[list.size()];
        int index = 0;
        for (Integer integer : list) {
            ints[index++] = integer;
        }
        Arrays.sort(ints);
        return ints;
    }


    /**
     * 面试题 02.03. 删除中间节点
     *
     * @param node
     */
    public void deleteNode(ListNode node) {

    }

    public void toGoatLatin(String str) {
    }
}

class MyQueue {
    private Stack<Integer> inStack;
    private Stack<Integer> outStack;

    /**
     * Initialize your data structure here.
     */
    public MyQueue() {
        inStack = new Stack<>();
        outStack = new Stack<>();
    }

    /**
     * Push element x to the back of queue.
     */
    public void push(int x) {
        inStack.push(x);
    }

    /**
     * Removes the element from in front of queue and returns that element.
     */
    public int pop() {
        if (redefineStack()) return -1;
        return outStack.pop();
    }

    /**
     * Get the front element.
     */
    public int peek() {
        if (redefineStack()) return -1;
        return outStack.peek();
    }

    private boolean redefineStack() {
        if (inStack.isEmpty() && outStack.isEmpty()) return true;
        if (outStack.isEmpty()) {
            for (int i = inStack.size() - 1; i >= 0; i--) {
                outStack.push(inStack.pop());
            }
        }
        return false;
    }

    /**
     * Returns whether the queue is empty.
     */
    public boolean empty() {
        return inStack.isEmpty() || outStack.isEmpty();
    }
}

class MyQueue2 {

    private Stack<Integer> numStack;
    private Stack<Integer> helpStack;

    public MyQueue2() {
        numStack = new Stack<>();
        helpStack = new Stack<>();
    }

    public void push(int x) {
        numStack.push(x);
    }

    public int pop() {
        peek();
        return helpStack.pop();
    }

    public int peek() {
        if (helpStack.isEmpty()) {
            while (!numStack.isEmpty()) {
                helpStack.push(numStack.pop());
            }
        }

        return helpStack.peek();
    }

    public boolean empty() {
        return helpStack.isEmpty() && numStack.isEmpty();
    }

    /**
     * 剑指 Offer 61. 扑克牌中的顺子
     *
     * @param nums
     * @return
     */
    public boolean isStraight(int[] nums) {
        Set<Integer> repeat = new HashSet<>();
        int max = 0, min = 14;
        for (int num : nums) {
            if (num == 0) continue;
            max = Math.max(max, num);
            min = Math.min(min, num);
            if (repeat.contains(num)) return false;
            repeat.add(num);
        }
        return max - min < 5;
    }

    /**
     * 剑指 Offer 61. 扑克牌中的顺子
     *
     * @param nums
     * @return
     */
    public boolean isStraight2(int[] nums) {
        int joker = 0;
        Arrays.sort(nums);
        for (int i = 0; i < 4; i++) {
            if (nums[i] == 0) joker++;
            else if (nums[i] == nums[i + 1]) return false;
        }
        return nums[4] - nums[joker] < 5;
    }


    /**
     * 643. 子数组最大平均数 I
     *
     * @param nums
     * @param k
     * @return
     */
    public static double findMaxAverage(int[] nums, int k) {
        int beginSum = 0;
        for (int i = 0; i < k; i++) {
            beginSum += nums[i];
        }
        int start = 0;
        int sum = Integer.MIN_VALUE;
        for (int i = k; i < nums.length; i++) {
            beginSum = beginSum - nums[start++] + nums[i];
            sum = Math.max(sum, beginSum);
        }
        return (double) sum / k;
    }

    /**
     * 1208. 尽可能使字符串相等
     *
     * @param s
     * @param t
     * @param maxCost
     * @return
     */
    public int equalSubstring(String s, String t, int maxCost) {
        char[] sChars = s.toCharArray();
        char[] tChars = t.toCharArray();
        int count = 0;
        int index = 0;
        while (index < sChars.length || index < tChars.length) {

        }
        return 0;
    }

    /**
     * 面试题 17.12. BiNode
     *
     * @param root
     * @return
     */
    public TreeNode convertBiNode(TreeNode root) {
        List<Integer> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        while (!queue.isEmpty()) {
            TreeNode node = queue.poll();
            if (node == null) {
                break;
            }
            list.add(node.val);
            if (node.left != null) {
                queue.offer(node.left);
            }
            if (node.right != null) {
                queue.offer(node.right);
            }
        }
        Collections.sort(list);

        for (int i = 0, len = list.size(); i < len; i++) {

        }
        return null;
    }

    /**
     * 500. 键盘行
     *
     * @param words
     * @return
     */
    public String[] findWords(String[] words) {
        Set<Character> setOne = stringToCharSet("qwertyuiop");
        Set<Character> setTwo = stringToCharSet("asdfghjkl");
        Set<Character> setThree = stringToCharSet("zxcvbnm");
        List<String> list = new ArrayList<>();
        for (String word : words) {
            boolean flagOne = false;
            boolean flagTwo = false;
            boolean flagThreee = false;
            for (char c : word.toCharArray()) {
                if (setOne.contains(c)) {
                    flagOne = true;
                }
                if (setTwo.contains(c)) {
                    flagTwo = true;
                }
                if (setThree.contains(c)) {
                    flagThreee = true;
                }
            }
            if (flagOne && !flagTwo && !flagThreee) {
                list.add(word);
                continue;
            }
            if (flagTwo && !flagOne && !flagThreee) {
                list.add(word);
                continue;
            }
            if (flagThreee && !flagOne && !flagTwo) {
                list.add(word);
            }
        }
        return list.toArray(new String[0]);
    }

    private Set<Character> stringToCharSet(String str) {
        Set<Character> set = new HashSet<>();
        for (char c : str.toCharArray()) {
            set.add(c);
        }
        return set;
    }


    /**
     * 434. 字符串中的单词数
     *
     * @param s
     * @return
     */
    public int countSegments(String s) {
        if (s == null || s.trim().length() == 0) return 0;
        char[] chars = s.trim().toCharArray();
        int count = 0;
        boolean flag = true;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] != ' ') {
                flag = true;
                continue;
            }
            if (flag) {
                count++;
                flag = false;
            }

        }
        return count;
    }

    /**
     * 104. 二叉树的最大深度 广度优先算法
     *
     * @param root
     * @return
     */
    public int maxDepth(TreeNode root) {
        if (root == null) return 0;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        int deep = 0;
        while (!queue.isEmpty()) {
            for (int i = 0, len = queue.size(); i < len; i++) {
                TreeNode node = queue.poll();
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            deep++;
        }
        return deep;
    }

    public static void main2(String[] args) {
        TreeNode root = new TreeNode(3);
        TreeNode rootLeft = new TreeNode(9);
        TreeNode rootRight = new TreeNode(20);
        TreeNode rootRL = new TreeNode(15);
        TreeNode rootRR = new TreeNode(7);
        root.left = rootLeft;
        root.right = rootRight;
        rootRight.left = rootRL;
        rootRight.right = rootRR;
        maxDepth2(root);
    }

    /**
     * 深度优先算法
     *
     * @param root
     * @return
     */
    public static int maxDepth2(TreeNode root) {
        if (root == null) return 0;
        else {
            int leftHeight = maxDepth2(root.left);
            System.out.println(leftHeight);
            int rightHeight = maxDepth2(root.right);
            System.out.println(rightHeight);
            return Math.max(leftHeight, rightHeight) + 1;
        }
    }


    /**
     * 258. 各位相加
     *
     * @param num
     * @return
     */
    public int addDigits(int num) {
        return 0;
    }

    /**
     * 520. 检测大写字母
     *
     * @param word
     * @return
     */
    public boolean detectCapitalUse(String word) {
        if (word == null || word.length() == 0) return true;
        char[] chars = word.toCharArray();
        //flag 第一个字母大写
        boolean flag = chars[0] < 97;
        //以后的字母默认大写
        boolean afterFlag1 = true;
        //以后的字母默认小写
        boolean afterFlag2 = true;
        for (int i = 1; i < chars.length; i++) {
            if (flag) {
                //首字母大写 其余字母大写
                if (chars[i] < 97) {
                    afterFlag2 = false;
                } else {
                    afterFlag1 = false;
                }
                if (!afterFlag1 && !afterFlag2) {
                    return false;
                }
            } else {
                //首字母小写 后面是大写
                if (chars[i] < 97) return false;
            }
        }
        return true;

    }

    /**
     * 1423. 可获得的最大点数
     *
     * @param cardPoints
     * @param k
     * @return
     */
    public int maxScore(int[] cardPoints, int k) {

        return 0;
    }

    public static void main3(String[] args) {
        int[] nums = {-1, 4, 2, 3};
        int[] nums2 = {3, 4, 2, 3}; //false
        checkPossibility(nums);
        checkPossibility(nums2);

    }


    /**
     * 665. 非递减数列
     *
     * @param nums
     * @return
     */
    public static boolean checkPossibility(int[] nums) {
        if (nums.length < 3) return true;
        int count = 0;
        int preValue = nums[0];
        for (int i = 1; i < nums.length; i++) {

        }
        return count < 2;
    }

    /**
     * 637. 二叉树的层平均值 广度优先算法
     *
     * @param root
     * @return
     */
    public List<Double> averageOfLevelsBFS(TreeNode root) {
        List<Double> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            int sum = 0;
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            list.add((double) sum / len);
        }
        return list;
    }

    /**
     * 637. 二叉树的层平均值 深度优先算法
     *
     * @param root
     * @return
     */
    public List<Double> averageOfLevelsDFS(TreeNode root) {
        List<Double> list = new ArrayList<>();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        while (!queue.isEmpty()) {
            int len = queue.size();
            int sum = 0;
            for (int i = 0; i < len; i++) {
                TreeNode node = queue.poll();
                sum += node.val;
                if (node.left != null) queue.offer(node.left);
                if (node.right != null) queue.offer(node.right);
            }
            list.add((double) sum / len);
        }
        return list;
    }

    /**
     * 107. 二叉树的层序遍历 II
     *
     * @param root
     * @return
     */
    public List<List<Integer>> levelOrderBottom(TreeNode root) {
        List<List<Integer>> lists = new ArrayList<>();
        if (root == null) return lists;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.offer(root);
        TreeNode node;
        List<Integer> list;
        while (!queue.isEmpty()) {
            int len = queue.size();
            list = new ArrayList<>(len);
            for (int i = 0; i < len; i++) {
                node = queue.poll();
                if (node.left != null) {
                    queue.offer(node.left);
                }
                if (node.right != null) {
                    queue.offer(node.right);
                }
                list.add(node.val);
            }
            lists.add(list);
        }
        Collections.reverse(lists);
        return lists;
    }

    /**
     * 70. 爬楼梯
     *
     * @param n
     * @return
     */
    public int climbStairs(int n) {
        if (n < 3) return n;
        int[] dp = new int[n + 1];
        dp[1] = 1;
        dp[2] = 2;
        for (int i = 3; i <= n; i++) {
            dp[i] = dp[i - 1] + dp[i - 2];
        }
        return dp[n];
    }

    /**
     * 70. 爬楼梯
     *
     * @param n
     * @return
     */
    public int climbStairs2(int n) {
        if (n < 3) return n;
        int ret = 0;
        int pre2 = 1;
        int pre = 2;
        for (int i = 3; i <= n; i++) {
            ret = pre + pre2;
            pre2 = pre;
            pre = i;
        }
        return ret;
    }

    /**
     * 70. 爬楼梯 递归
     *
     * @param n
     * @return
     */
    public int climbStairs3(int n) {
        if (n == 1) return 1;
        if (n == 2) return 2;
        return climbStairs(n - 1) + climbStairs(n - 2);
    }

    /**
     * 521. 最长特殊序列 Ⅰ
     *
     * @param a
     * @param b
     * @return
     */
    public int findLUSlength(String a, String b) {
        if (a.equals(b)) return -1;
        return Math.max(a.length(), b.length());
    }


    /**
     * 541. 反转字符串 II
     *
     * @param s
     * @param k
     * @return
     */
    public static String reverseStr(String s, int k) {
        if (s.length() < k) return new StringBuilder(s).reverse().toString();
        char[] chars = s.toCharArray();
        int doubleK = k << 1;
        int div = chars.length / doubleK;
        int mod = chars.length % doubleK;
        int startIndex = 0;
        int endIndex = k;
        while (div-- > 0) {
            reverserByStartAndEndIndex(chars, startIndex, endIndex);
            startIndex += doubleK;
            endIndex = startIndex + k;
        }
        if (mod == 0) return new String(chars);
        if (mod < k) {
            reverserByStartAndEndIndex(chars, startIndex, chars.length);
            return new String(chars);
        }
        reverserByStartAndEndIndex(chars, startIndex, endIndex);
        return new String(chars);
    }

    private static void reverserByStartAndEndIndex(char[] chars, int startIndex, int endIndex) {
        endIndex--;
        while (startIndex < endIndex) {
            char temp = chars[startIndex];
            chars[startIndex] = chars[endIndex];
            chars[endIndex] = temp;
            startIndex++;
            endIndex--;
        }
    }

//    public static void main(String[] args) {
//        int[] nums = {1,2,2,3,1,4,2};
//        int[] nums2 = {1, 2, 2, 3, 1};
//        System.out.println(findShortestSubArray(nums2));
//    }

    /**
     * 697. 数组的度
     *
     * @param nums
     * @return
     */
    public static int findShortestSubArray(int[] nums) {
        if (nums.length == 1) return nums.length;
        //统计数字num对应的pinglv
        Map<Integer, Integer> map = new HashMap<>(nums.length);
        for (int num : nums) {
            map.put(num, map.getOrDefault(num, 0) + 1);
        }
        //找出频率最大值
        int maxCount = 0;
        //找出最大值的num
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            maxCount = Math.max(entry.getValue(), maxCount);
        }
        if (maxCount == 1) return 1;
        //记录频率最大的
        List<Integer> list = new ArrayList<>();
        for (Map.Entry<Integer, Integer> entry : map.entrySet()) {
            if (entry.getValue() == maxCount) list.add(entry.getKey());
        }
        //然后前后查找定位
        int minLength = Integer.MAX_VALUE;
        for (Integer integer : list) {
            int startIndex = 0;
            int endIndex = nums.length - 1;
            int tempStartIndex = startIndex;
            int tempEndIndex = endIndex;
            boolean startFlag = true;
            boolean endFlag = true;
            while (startIndex <= endIndex) {
                if (!startFlag && !endFlag) {
                    break;
                }
                if (startFlag && nums[startIndex] == integer) {
                    tempStartIndex = startIndex;
                    startFlag = false;
                }
                if (endFlag && nums[endIndex] == integer) {
                    tempEndIndex = endIndex;
                    endFlag = false;
                }
                startIndex++;
                endIndex--;
            }
            minLength = Math.min(tempEndIndex - tempStartIndex + 1, minLength);
        }
        return minLength;
    }

//    public static void main(String[] args) {
//        Integer[] arr = new Integer[1];
//        System.out.println(Arrays.toString(arr));
//
//        String s = "loveleetcode";
//        shortestToChar(s, 'e');
//    }


    /**
     * 821. 字符的最短距离
     *
     * @param s
     * @param c
     * @return
     */
    public static int[] shortestToChar(String s, char c) {
        char[] chars = s.toCharArray();
        int[] retArr = new int[chars.length];
        Arrays.fill(retArr, -1);
        int count = 0;
        boolean flag = false;
        for (int i = 0; i < chars.length; i++) {
            if (chars[i] == c) {
                flag = true;
                count = 0;
                retArr[i] = count;
                continue;
            }
            if (flag) {
                retArr[i] = ++count;
            }
        }
        count = 0;
        flag = false;
        for (int i = chars.length - 1; i >= 0; i--) {
            if (chars[i] == c) {
                flag = true;
                count = 0;
                continue;
            }
            if (flag) {
                if (retArr[i] != -1) {
                    retArr[i] = Math.min(++count, retArr[i]);
                } else {
                    retArr[i] = ++count;
                }
            }
        }
        return retArr;
    }

    public static void main(String[] args) {
        String str = "The quick brown fox jumped over the lazy dog";

        MyQueue2 demo21 = new MyQueue2();
        demo21.toGoatLatin(str);
    }


    /**
     * 824. 山羊拉丁文
     *
     * @param S
     * @return
     */
    public String toGoatLatin(String S) {
        int[] arr = getArrCharacters();
        String[] strings = S.split(" ");
        StringBuilder sb = new StringBuilder();
        int count = 1;
        for (String string : strings) {
            char headChar = string.charAt(0);
            if (arr[headChar] > 0) {
                sb.append(string);
            } else {
                sb.append(string.substring(1));
                sb.append(headChar);
            }
            sb.append("ma");
            for (int i = 0; i < count; i++) {
                sb.append("a");
            }
            sb.append(" ");
            count++;
        }
        return sb.substring(0, sb.length() - 1).toString();
    }

    private Set<Character> getCharacters() {
        Set<Character> set = new HashSet<>();
        set.add('a');
        set.add('e');
        set.add('i');
        set.add('o');
        set.add('u');
        set.add('A');
        set.add('E');
        set.add('I');
        set.add('O');
        set.add('U');
        return set;
    }
    private int[] getArrCharacters() {
        int[] ints = new int[123];
        ints['a']++;
        ints['e']++;
        ints['i']++;
        ints['o']++;
        ints['u']++;
        ints['A']++;
        ints['E']++;
        ints['I']++;
        ints['O']++;
        ints['U']++;
        return ints;
    }
}

class A {
    private String name;

    private Integer age;

    public A() {
    }

    public A(String name, Integer age) {
        this.name = name;
        this.age = age;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public Integer getAge() {
        return age;
    }

    public void setAge(Integer age) {
        this.age = age;
    }

    @Override
    public String toString() {
        return "A{" +
                "name='" + name + '\'' +
                ", age=" + age +
                '}';
    }
}

class AnimalShelf {

    private Queue<int[]> catQueue;
    private Queue<int[]> dogQueue;

    public AnimalShelf() {
        catQueue = new LinkedList<>();
        dogQueue = new LinkedList<>();
    }

    public void enqueue(int[] animal) {
        if (animal[1] == 0) {
            catQueue.offer(animal);
        } else {
            dogQueue.offer(animal);
        }
    }

    public int[] dequeueAny() {
        if (catQueue.isEmpty() && dogQueue.isEmpty()) return new int[]{-1, -1};
        if (catQueue.isEmpty()) {
            return dequeueDog();
        }
        if (dogQueue.isEmpty()) {
            return dequeueCat();
        }
        int[] cat = catQueue.peek();
        int[] dog = dogQueue.peek();
        if (cat[0] > dog[0]) {
            return dequeueCat();
        }
        return dequeueDog();
    }

    public int[] dequeueDog() {
        if (dogQueue.isEmpty()) return new int[]{-1, -1};

        return dogQueue.poll();
    }

    public int[] dequeueCat() {
        if (catQueue.isEmpty()) return new int[]{-1, -1};
        return catQueue.poll();
    }


}